package main

import "fmt"

func main() {
	fmt.Println(jump2([]int{2, 3, 1, 1, 4}))
	fmt.Println(jump([]int{2, 3, 0, 0, 4}))
	fmt.Println(jump2([]int{9, 8, 7, 6, 5, 4, 3, 2, 3, 0, 0, 4}))
}

func jump(nums []int) int {
	dpTab := make([]int, len(nums))
	for k, v := range nums {
		if k == len(nums)-1 {
			break
		}
		for i := k + 1; i <= k+v && i < len(nums); i++ {
			if dpTab[i] == 0 {
				dpTab[i] = dpTab[k] + 1
			} else {
				if dpTab[i] > dpTab[k]+1 {
					dpTab[i] = dpTab[k] + 1
				}
			}
		}
	}
	return dpTab[len(dpTab)-1]
}

func jump1(nums []int) int {
	dp := make([]int, len(nums))
	dp[0] = 0
	for i := 1; i < len(dp); i++ {
		for j := 0; j < i; j++ {
			if nums[j]+j >= i {
				if dp[i] == 0 {
					dp[i] = dp[j] + 1
				} else {
					if dp[i] > dp[j]+1 {
						dp[i] = dp[j] + 1
					}
				}

			}
		}
	}
	return dp[len(dp)-1]

}

func jump2(nums []int) int {
	dp := make([]int, len(nums))
	for i := 0; i < len(nums)-1; i++ {
		for j := i + 1; j <= i+nums[i]; j++ {
			if dp[j] == 0 {
				dp[j] = dp[i] + 1
			} else if dp[j] > dp[i]+1 {
				dp[j] = dp[i] + 1
			}
		}
	}
	return dp[len(dp)-1]

}

func jump3(nums []int) int {
	for i := 0; i < len(nums)-1; i++ {

	}
}
